Validate Binary Search Tree

Leetcode #98 | Medium | Деревья | DFS | BST

Идея

DFS с границами low и high. Если нода null - true, если значение ноды вне low...high - false. При спуске влево родитель задает ограничение сверху (high), при спуске вправо - ограничение снизу (low) - свойства бинарного дерева.
Важно: изначально high и low нужно ставить в Long.MAX_VALUE/Long.MIN_VALUE (по требованиям задачи, Integer слишком маленький)

Big-O

• Время O(N)
• Память O(H)

N - количество узлов, H - высота дерева

Код

class Solution {
    public boolean isValidBST(TreeNode root) { return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE); }
    private boolean dfs(TreeNode node, long low, long high) {
        if (node == null) return true;
        if (node.val <= low || node.val >= high) return false;
        return dfs(node.left, low, node.val) && dfs(node.right, node.val, high);
    }
}